1. Field of the Invention
This invention relates to tag comparators for buffers and, more particularly, to tag comparators for finite wrap-around buffers.
2. Description of the Relevant Art
A finite wrap-around buffer is a data storage device that stores data words of a fixed width. The buffer typically stores 2.sup.n data words or entries. Each entry in the buffer stores a tag. The tags typically have a value between 0 to 2.sup.n-1. The tags are continuous, or sequential, and are typically generated by a n-bit incrementor. For example, if the buffer has sixteen entries, then the tags have a value from 0 to 15 and are generated by a four-bit incrementor. The tags, however, do not always start with 0 and may wrap-around in the buffer space. For example, the first entry in the buffer may store a tag of 11. The next entries would be continuous, i.e., tag values of 12, 13, 14, and 15. At this point, the tag has reached its maximum value of 15, and the tag wraps-around to 0, followed by 1, 2, 3 etc.
In some systems, a cancel operation deletes all tags in the buffer with a tag value "greater-than" a specific tag value (the specific tag value is called a cancel tag). The "greater-than" condition, however, must take in to account the wrap-around feature of the buffer. For example, if the tags range for 9 to 3 (i.e. 9, 10, 11, 12, 13, 14, 15, 0, 1, 2 and 3) and the cancel tag is 14, then tags 15, 0, 1, 2 and 3 would be canceled. In this case, 1 is considered "greater than" 14.
The first step in the conventional solution to determining which entries are "greater-than" the cancel tag is to determine if a wrap-around condition occurs in the buffer. If a wrap-around condition does exist, the tags before the wrap-around are canceled if they are greater-than the cancel tag, and the tags after the wrap-around are canceled if they are less-than the cancel tag. The process of detecting a wrap-around condition, however, takes up a significant amount of logic and introduces a significant delay. This delay may be critical in high frequency superscalar microprocessor designs.
A wrap-around buffer that supports a cancel operation without the overhead and delay of a typical wrap-around condition detector is thus desired.